The field of the present invention relates to electronic design automation and, more particularly, to methods and mechanisms for performing improved timing analysis upon electronic circuit blocks.
Advances in silicon technology increasingly allow larger and more complex designs to be formed on a single chip. Designs may consist of millions or tens of millions of transistors on a single chip. At the same time, however, market demands continue to push designers to develop designs more rapidly and efficiently. A recent trend to increase design speed and efficiency involves the re-use or recycling of electronic circuit models of circuit blocks (which may have one or more subsystems), which are commonly referred to as xe2x80x9ccoresxe2x80x9d or xe2x80x9cIPsxe2x80x9d (for xe2x80x9cIntellectual Propertiesxe2x80x9d). Once the design for a circuit block has been tested and verified, it can be re-used in other applications which may be completely distinct from the application which led to its original creation. For example, a subsystem for a cellular phone ASIC may contain a micro-controller as well as a digital signal processor and other components. After the design for the cellular phone subsystem has been tested and verified, the circuit block could be re-used in, for example, an automotive application. Design reuse of circuit blocks allows a designer to complete a design much faster than building the entire design from scratch, and avoids the need for debugging, testing and verification of the subsystems embodied circuit block. Circuit blocks may be of various sizes and levels of complexity, and one circuit block may comprise one or more subsystems, where each subsystem is itself a circuit block. A virtual component block shall be used herein to refer to any model or abstract representation of a circuit block.
Timing models may be used to characterize the timing of a circuit block without having access to the actual circuit block once the timing model is constructed. While timing models have been found to be convenient for expediting and simplifying the circuit design process, the successful use of timing models hinges on the ability to accurately characterize their timing and functionality. In analyzing large circuits, it is often necessary to sacrifice some accuracy given the computational complexity involved, e.g., some methods of timing analysis performed on circuits consider false paths. False paths are signal paths that are never sensitized, i.e., activated, in actual operation. While it may be possible to detect false paths, identifying and removing them when undergoing timing analysis on large circuits is much too slow to be of practical value.
A number of techniques have been developed or proposed for performing timing estimation analyses on circuit blocks, including static timing analysis and functional timing analysis. Static timing analysis involves the calculation of a worst-case structural (or topological) delay between a circuit block""s input and an output, but ignores the functionality of the circuit block. Static timing analysis methods make no attempt to detect false paths.
Functional timing analysis methods attempt to rely on the fact that the delays in a circuit block are linked to the way a circuit functions. xe2x80x9cFunctionalityxe2x80x9d in this context refers to the logical value computed for each node in the circuit block (xe2x80x9ccircuit nodexe2x80x9d), given an input vector. Unlike traditional static timing analysis, functional timing analysis uses a circuit block""s function as well as its structure to characterize delays and timing constraints.
Two widely used methods for functional timing analysis are symbolic analysis via binary-decision diagrams (BDDs), and boolean search methodologies that systematically enumerate the input space. Both methods assume that the delays of a circuit block depend on the values of all of its inputs. These methods aim at finding an input vector that sensitizes the true longest path. However, they both have the disadvantage that their complexity increases exponentially with circuit size, limiting their applicability, or requiring unacceptably large amounts of computation resources for larger circuit designs.
A more practical approach is to assume that a circuit block""s delay depend on only a subset of its inputs. This is typical of datapath circuits, where a small number of control inputs determine the delays between a large number of data inputs and data outputs. A simple example is shown by a circuit 50 in FIG. 1, wherein the control inputs 60 to a large extent determine the delays between the data inputs 55 and the data outputs 70. For example, if the control inputs 60 sensitize the signal path to enable operation 1, then a delay of 10 is observed, while only a delay of 2 is observed if operation 3 is performed.
Methods of timing analysis have been developed based upon the recognition that the control inputs play a role in determining the delays between the data inputs and outputs. These methods generally trade accuracy for computation efficiency. For example, some static timing analyzers employ a systematic case analysis capability whereby the user sets some inputs to constant values prior to performing the timing analysis. A drawback with such timing analysis methods is that they suffer from delay underestimation. Delay underestimation is a serious problem in circuit design because it can lead to incorrect operation.
One timing analysis benchmark involves calculation of the delay in a so-called xe2x80x9cfloating modexe2x80x9d of operation. In a floating mode of operation, each circuit node initially has an unknown value. Upon the application of an input vector to the circuit, the circuit node undergoes a series of transitions or events before it eventually stabilizes at a value determined by the circuit""s internal static functionality.
Examples of event propagation using principles of xe2x80x9ccontrollingxe2x80x9d and xe2x80x9cnon-controllingxe2x80x9d values are illustrated in FIGS. 2A and 2B, for the simple case of a two-input AND gate. A controlling value (CV) at a gate input is one that determines the output of the gate regardless of the values of the other inputs. A non-controlling value (NCV) does not change the gate output by itself. For an AND gate, the controlling and non-controlling values are 0 and 1, respectively. The arrival time of a gate output is determined by the earliest input with a controlling value, if it exists; otherwise, the latest input with the non-controlling value determines the output arrival time. In FIG. 2A, input xe2x80x9caxe2x80x9d is a controlling value because it will eventually become 0, whereas in FIG. 2B, neither input xe2x80x9caxe2x80x9d nor xe2x80x9cbxe2x80x9d is a controlling value because both will stay at 1. Because, input xe2x80x9caxe2x80x9d has a controlling value in FIG. 2A, the gate output arrival time xe2x80x9cTzxe2x80x9d is determined only by the arrival time Ta of input xe2x80x9caxe2x80x9d, plus the gate delay d. In FIG. 2B, however, because neither input xe2x80x9caxe2x80x9d nor xe2x80x9cbxe2x80x9d has a controlling value, the output arrival time Tz is given by the latest input arrival time (in this example, Tb) plus the gate delay d. Because the last arriving event at any node determines the delay up to that node, the terms xe2x80x9carrival timexe2x80x9d and xe2x80x9cdelayxe2x80x9d are used interchangeably herein.
For a generic gate having inputs xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d and output xe2x80x9czxe2x80x9d in floating mode (FM), these concepts may be shown in the form of a truth table, TzFM, such as appearing in Table 1 below.
It is possible to write a logical expression (or predicate) that describes whether an input event propagates from a gate input to the gate output; such expressions are sometimes referred to as xe2x80x9csensitization conditionsxe2x80x9d or xe2x80x9cpropagation conditions.xe2x80x9d Referring back to FIGS. 2A and 2B, the sensitization condition for the path from input xe2x80x9caxe2x80x9d to gate output xe2x80x9czxe2x80x9d may be denoted CONDaz. In FIG. 2A, analyzing the path of the gate using floating mode propagation condition, the path is xe2x80x9csensitized,xe2x80x9d so CONDaz is 1 (true). In FIG. 2B, again analyzing the path of the gate using floating mode propagation condition, the path is not xe2x80x9csensitized,xe2x80x9d so CONDaz is 0 (false). A number of propagation conditions have been proposed. Two such propagation conditions, referred to as xe2x80x9cviabilityxe2x80x9d and xe2x80x9cfloating-mode condition,xe2x80x9d have been used in calculating the floating-mode arrival time of Table 1. The values of TzFM shown in Table 1 are the least pessimistic that can be achieved in xe2x80x9cfloating mode.xe2x80x9d Thus, for any conditional expression TzX to be correct for delay calculation using the conventional xe2x80x9cfloating modexe2x80x9d conditional analysis, it must exceed the delay values expressed in Table 1 above; that is, it must satisfy the relationship:
Txzxe2x89xa7TzFM∀vaxe2x80x2∀vb
Several other propagation conditions have been proposed. xe2x80x9cStatic sensitizationxe2x80x9d is a commonly used sensitization condition that has arisen from test generation. Static sensitization is based on the premise that a path is xe2x80x9csensitizedxe2x80x9d only if all its side inputs (i.e., inputs of a gate that are not on the delay path) have non-controlling values. A computational advantage of this condition is that it depends only on the final (stable) values of the inputs and is independent of the input event times. However, a drawback of static sensitization techniques is that, if the two inputs of a gate are controlling, they incorrectly assume that the paths from both inputs are false.
In contrast to static sensitization, the simplest (but most pessimistic) path propagation condition is that of topological analysis where events always propagate. Thus, for the two-input gate case, the output arrival time, which may be designated TzTOP, is always the maximum of the input event times plus the gate delay. Table 2 below summarizes and compares the arrival times for floating mode, static sensitization, and topological analysis.
In Table 2, the term xe2x80x9cxe2x88x92∞xe2x80x9d indicates that no event propagates; hence, an effectively xe2x80x9cinfinitexe2x80x9d delay. As may be observed from viewing Table 2, the output arrival time TzTOP under a topological analysis where events always propagate is always greater than or equal to the output arrival time TzFM using floating mode conditional analysis. Topological analysis is commonly used in static timing analysis tools. A big disadvantage is its failure to detect any false paths, leading to overly pessimistic results.
Therefore, a need exists for a functional timing analysis of circuit blocks that has improved accuracy, yet is not computationally burdensome.
Accordingly, the present invention provides for a method and mechanism for performing improved timing analysis on virtual component blocks. In an embodiment, a method of analyzing timing in a circuit block, where the circuit block includes a plurality of inputs and one or more outputs, and where the plurality of inputs divided into a set of one or more data inputs and a set of one or more control inputs, includes (a) identifying a set of modes, each of the modes corresponding to a unique combination of control input values for the circuit block; (b) applying the combination of control input values for one of said modes to the circuit block; (c) for each data input, calculating a first delay for each data input/output path not passing through a blocked circuit node for the applied combination of control input values using a first propagation condition; (d) for each control input, calculating a second delay for each control input/output path not passing through a blocked circuit node for the applied combination of control input values using a second propagation condition; and (e) repeating steps (b) through (d) for each of the remaining modes within the set of modes. Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims.